package com.sicheng.lc.周赛.分类.并差集;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/1 23:21
 */
public class 字符串分组 {
    //https://leetcode.cn/problems/groups-of-strings/

    HashMap<Integer, Integer> p = new HashMap<>(), cnt = new HashMap<>();
    int size;

    int find(int x) {
        int px = p.get(x);
        if (px == x)
            return px;
        int ppx = find(px);
        p.put(x, ppx);
        return ppx;
    }

    void union(int a, int b) {
        if (!p.containsKey(a) || !p.containsKey(b)) {
            return;
        }
        int pa = find(a);
        int pb = find(b);
        if (pa != pb) {
            p.put(pb, pa);
            cnt.put(pa, cnt.get(pa) + cnt.get(pb));
            size--;
        }
    }

    public int[] groupStrings(String[] words) {
        size = words.length;
        int m = -1;
        for (String word : words) {
            int x = 0;
            for (int i = 0; i < word.length(); i++) {
                x |= 1 << word.charAt(i) - 'a';
            }
            p.put(x, x);
            int c = cnt.getOrDefault(x, 0);
            if (c > 0)
                size--;
            cnt.put(x, c + 1);
        }

        p.forEach((x, px) -> {
            // 删除或者添加一个字符
            for (int i = 0; i < 26; i++) {
                union(x, x ^ (1 << i));
                for (int j = 0; j < 26; j++) {
                    if ((x >> i & 1) == 1) {
                        // 替换字符
                        union(x, x ^ (1 << i) | (1 << j));
                    }
                }
            }
        });


        for (Map.Entry<Integer, Integer> entry : p.entrySet()) {
            int x = entry.getKey();
            if (x == entry.getValue()) {
                m = Math.max(m, cnt.get(x));
            }
        }

        return new int[]{size, m};
    }
}
